/* 120. 三角形最小路径和 */
/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = (triangle) => {
    const h = triangle.length;
    // 初始化dp数组
    const dp = new Array(h);
    for (let i = 0; i < h; i++) {
        dp[i] = new Array(triangle[i].length);
    }

    for (let i = h - 1; i >= 0; i--) { // 自底而上遍历
        for (let j = 0; j < triangle[i].length; j++) { // 同一层的
            if (i == h - 1) {  // base case 最底层
                dp[i][j] = triangle[i][j];
            } else { // 状态转移方程，上一层由它下面一层计算出
                dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];
            }
        }
    }
    return dp[0][0];
};


/* 降维后的dp */
var minimumTotal = function (triangle) {
    const bottom = triangle[triangle.length - 1]
    const dp = new Array(bottom.length).fill(0).map((_, i) => bottom[i])

    /* 倒数第二列开始 */
    for (let i = dp.length - 2; i >= 0; i--) {
        for (let j = 0; j < triangle[i].length; j++) {
            dp[j] = Math.min(dp[j], dp[j + 1]) + triangle[i][j]
        }
    }


    return dp[0]
}
const res = minimumTotal([[-1], [2, 3], [1, -1, -3]])
console.log("res :>>", res);